package hasthi.common;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class Cube<T> {
    private CubeEntry head = null;

    public Cube() {
    }

    private class CubeEntry {
        String x;
        String y;
        String z;
        CubeEntry xleft = null;
        CubeEntry xright = null;
        CubeEntry yup = null;
        CubeEntry ydown = null;
        CubeEntry zin = null;
        CubeEntry zout = null;
        T value;

        public CubeEntry(String x, String y, String z, T value) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.value = value;
        }

        public void copy(CubeEntry entry) {
            this.x = entry.x;
            this.y = entry.y;
            this.z = entry.z;
            this.value = entry.value;
        }

        @Override
        public String toString() {
           return "("+x + "," +y + ","+z + ")->"+value;
        }
    }

    public T add(String xkey, String ykey, String zkey, T value) {
        if (head == null) {
            head = new CubeEntry(xkey, ykey, zkey, value);
            return null;
        }
        // X check
        CubeEntry current = head;
        while (true) {
            int test = xkey.compareTo(current.x);
            if (test == 0) {
                //new object is equal
                break;
            } else if (test < 0) {
                //new object is less
                if (current.xleft == null) {
                    current.xleft = new CubeEntry(xkey, ykey, zkey, value);
                    //current.xleft.xright = current;
                    return null;
                } else {
                    current = current.xleft;
                }
            } else{
                //new object is greater
                if (current.xright == null) {
                    current.xright = new CubeEntry(xkey, ykey, zkey, value);
                    //current.xright.xleft = current;
                    return null;
                } else {
                    current = current.xright;
                }
            }
        }
        // Y Check
        while (true) {
            int test = ykey.compareTo(current.y);
            if (test == 0) {
                //new object is equal
                break;
            } else if (test < 0) {
                //new object is less                
                if (current.ydown == null) {
                    current.ydown = new CubeEntry(xkey, ykey, zkey, value);
                    return null;
                } else {
                    current = current.ydown;
                }
            } else {
                //new object is greater
                if (current.yup == null) {
                    current.yup = new CubeEntry(xkey, ykey, zkey, value);
                    return null;
                } else {
                    current = current.yup;
                }
            }
        }
        // Z Check
        while (true) {
            int test = zkey.compareTo(current.z);
            if (test == 0) {
                //new object is equal
                T oldVal = current.value;
                //System.out.println("Hash collision "+ oldVal);
                current.copy(new CubeEntry(xkey, ykey, zkey, value));
                return oldVal;
            } else if (test < 0) {
                //new object is less                
                if (current.zin == null) {
                    current.zin = new CubeEntry(xkey, ykey, zkey, value);
                    return null;
                } else {
                    current = current.zin;
                }
            } else {
                //new object is grater
                if (current.zout == null) {
                    current.zout = new CubeEntry(xkey, ykey, zkey, value);
                    return null;
                } else {
                    current = current.zout;
                }
            }
        }

    }
    
    
    public T find(String xkey, String ykey, String zkey) {
        if (head == null) {
            return null;
        }

        // X check
        CubeEntry current = head;
        while (true) {
            int test = xkey.compareTo(current.x);
            if (test == 0) {
                break;
            } else if (test < 0) {
                if (current.xleft == null) {
                    return null;
                } else {
                    current = current.xleft;
                }
            } else if (test > 0) {
                if (current.xright == null) {
                    return null;
                } else {
                    current = current.xright;
                }
            }
        }
        // Y Check
        while (true) {
            int test = ykey.compareTo(current.y);
            if (test == 0) {
                break;
            } else if (test < 0) {
                if (current.ydown == null) {
                    return null;
                } else {
                    current = current.ydown;
                }
            } else if (test > 0) {
                if (current.yup == null) {
                    return null;
                } else {
                    current = current.yup;
                }
            }
        }
        // Z Check
        while (true) {
            int test = zkey.compareTo(current.z);
            if (test == 0) {
                return current.value;
            } else if (test < 0) {
                if (current.zin == null) {
                    return null;
                } else {
                    current = current.zin;
                }
            } else if (test > 0) {
                if (current.zout == null) {
                    return null;
                } else {
                    current = current.zout;
                }
            }
        }

    }
    
    
    public Iterator<T> find(String xkey, String ykey) {
        if (head == null) {
            return null;
        }

        // X check
        CubeEntry current = head;
        while (true) {
            int test = xkey.compareTo(current.x);
            if (test == 0) {
                break;
            } else if (test < 0) {
                if (current.xleft == null) {
                    return null;
                } else {
                    current = current.xleft;
                }
            } else if (test > 0) {
                if (current.xright == null) {
                    return null;
                } else {
                    current = current.xright;
                }
            }
        }
        // Y Check
        while (true) {
            int test = ykey.compareTo(current.y);
            if (test == 0) {
                break;
            } else if (test < 0) {
                if (current.ydown == null) {
                    return null;
                } else {
                    current = current.ydown;
                }
            } else if (test > 0) {
                if (current.yup == null) {
                    return null;
                } else {
                    current = current.yup;
                }
            }
        }
        return new ZIterator(current);
    }
    
    
    public List<String> firstKeySet() {
        Stack<CubeEntry> stack = new Stack<CubeEntry>();
        stack.push(head);
        
        ArrayList<String> keys = new ArrayList<String>();
        while(!stack.empty()){
            CubeEntry entry = stack.pop();
            if (entry.xleft != null) {
                stack.push(entry.xleft);
            } 
            if(entry.xright != null){
                stack.push(entry.xright);
            }
            keys.add(entry.x); 
        }
        return keys;
    }
    
    
    public Iterator<T> find(String xkey) {
        if (head == null) {
            return null;
        }
        // X check
        CubeEntry current = head;
        while (true) {
            int test = xkey.compareTo(current.x);
            if (test == 0) {
                break;
            } else if (test < 0) {
                if (current.xleft == null) {
                    return null;
                } else {
                    current = current.xleft;
                }
            } else if (test > 0) {
                if (current.xright == null) {
                    return null;
                } else {
                    current = current.xright;
                }
            }
        }
        return new YZIterator(current);
    }
    
    
    public Iterator<T> getAllNodes(){
        return new XYZIterator(head);
    }

    
    
    private class ZIterator implements Iterator<T>{
        private Stack<CubeEntry> stack = new Stack<CubeEntry>();
        
        public ZIterator(CubeEntry start){
            stack.push(start);
        }
        
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        public T next() {
            CubeEntry entry = stack.pop();
            if(entry.zin != null){
                stack.push(entry.zin);
            }
            if(entry.zout != null){
                stack.push(entry.zout);
            }
            return entry.value;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    private class YZIterator implements Iterator<T>{
        private Stack<CubeEntry> stack = new Stack<CubeEntry>();
        
        public YZIterator(CubeEntry start){
            stack.push(start);
        }
        
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        public T next() {
            CubeEntry entry = stack.pop();
            if(entry.zin != null){
                stack.push(entry.zin);
            }
            if(entry.zout != null){
                stack.push(entry.zout);
            }
            if(entry.yup != null){
                stack.push(entry.yup);
            }
            if(entry.ydown != null){
                stack.push(entry.ydown);
            }
            return entry.value;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    
    private class XYZIterator implements Iterator<T>{
        private Stack<CubeEntry> stack = new Stack<CubeEntry>();
        
        public XYZIterator(CubeEntry start){
            stack.push(start);
        }
        
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        public T next() {
            CubeEntry entry = stack.pop();
            if(entry.xleft != null){
                stack.push(entry.xleft);
            }
            if(entry.xright != null){
                stack.push(entry.xright);
            }
            if(entry.zin != null){
                stack.push(entry.zin);
            }
            if(entry.zout != null){
                stack.push(entry.zout);
            }
            if(entry.yup != null){
                stack.push(entry.yup);
            }
            if(entry.ydown != null){
                stack.push(entry.ydown);
            }
            return entry.value;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    public void travelAndPrint(){
        List<String> keyset = firstKeySet();
        for(String key:keyset){
            System.out.println(key);
        }
        System.out.println(keyset.size() + " elements");
        //System.out.println("Node count "+ count);
    }
    
    
}
